DS4IR

Análise de Redes

Professor Davi Moreira

Professor Rafael Magalhães

29-07-2020

Programa

  1. A análise de redes
  2. Principais medidas de centralidade
  3. Redes dirigidas e não dirigidas

Análise de dados do Twitter

Folha

A análise de redes

A análise de redes é aplicada para descrever relações entre nossas observações de interesse. As relações podem ser de amizade entre pessoas, trocas comerciais entre países, conexão entre atividades no planejamento estratégico de uma empresa, citações e co-autoria em artigos, etc.

Através da análise de redes obtemos novas estatísticas sobre os dados que temos e potencializamos nossas conclusões através das visualizações.

Undirected Network

Rede de Casamentos na Florença Renascentista

O objeto florence retrata uma matriz de adjacência, cujos elementos representam a relação entre duas unidades presentes nas linhas e colunas. Nesse caso, tratam-se de 16 famílias da elite Florentina e a existência de casamentos entre elas.

Robust Action and the Rise of the Medici, 1400-1434

Rede de Casamentos na Florença Renascentista

  • Essa matriz de adjacência representa uma rede não direcionada. Poderíamos adicionar direção caso tivéssemos, por exemplo, a informação de qual família propôs o casamento.

  • Sem direcionamento, tanto as linhas quanto as colunas apresentam as mesmas informações:

Rede de Casamentos na Florença Renascentista

florence

Rede de Casamentos na Florença Renascentista

Percebam que a rede é composta por nodes (nós/vértices) e edges (arestas), sendo esse o seu formato clássico de visualização. Com eles, podemos obter as principais medidas da análise de redes, as medidas de centralidade:

  • degree: medida mais elemntar. Representa quanto um nó é conectado aos demais. Ela simplesmente computa o número de edges que cada nó possui.

Rede de Casamentos na Florença Renascentista

  • farness: computa a soma de edges de um dado nó para todos os demais nós da rede. Descreve quão isolado cada node está dos demais.

  • closeness: a distância entre dois nós é representada pelo número de edges que os conectam pelo menor caminho possível. A medida closeness retrata quantas etapas um nó específico precisa para acessar todos os outros nós da rede.

\[ closeness(v) = \frac{1}{farness(v)} = \frac{1}{\sum_{u \in V, u\neq v}\text{distância entre} \quad v \quad \mathrm{e} \quad u} \]

Rede de Casamentos na Florença Renascentista

\[ closeness(v) = \frac{1}{farness(v)} = \frac{1}{\sum_{u \in V, u\neq v}\text{distância entre} \quad v \quad \mathrm{e} \quad u} \] Uma outra forma de olha para a centralidade é dividir farness pelo número de demais nós na rede. Podemos ver, por exemplo, que, em média, a família Medici está a 2,7 edges de cada nó da rede.

Rede de Casamentos na Florença Renascentista

  • betweenness: nesse caso, um nó é considerado central na medida em que ele permite conectar outros nós.

\[ betweenness(v) = \sum_{(t, u) \in V, t\neq u, u \neq v}\frac{\text{n de caminhos que contêm o nó} \quad v}{\text{n de caminhos entre} \quad t \quad e \quad u} \]

Vemos que a família Médici se localiza no menor caminho entre mais de 45% de todos os possíveis caminhos entre os outros nós.

Exercício:

Com o resultado de betweenness(florence_ntw), produza um gráfico de barras.

Exercício: resposta

Rede de Casamentos na Florença Renascentista

Comparando medidas de centralidade:

Rede de Casamentos na Florença Renascentista

undir

Directed Network

Twitter Following Network

  • Objeto twitter: temos a informação dos senadores que cada senador segue.
  • Objeto senator: informações sobre cada senador.

Twitter Following Network

Vamos criar nossa matriz de adjacência com o objeto twitter. Percebam que ela é assimétrica.

Twitter Following Network

Em redes direcionadas como essa, podemos analisar as medidas já vistas. Porém, agora temos dois tipos de degree, por exemplo:

  1. Indegree: a soma de edges que chegam a um nó. Em outras palavras, o número de seguidores.
  2. Outdegree: a soma de edges que saem de um nó. Ou seja, o número de nós que um determinado nó segue.

dir-d

Twitter Following Network

Podemos calcular as duas medidas e atribuí-las ao nosso objeto senator.

Twitter Following Network

Agora temos dois tipos de closeness: indegree e outdegree.

dir-c

Twitter Following Network

Podemos calcular as duas medidas e atribuí-las ao nosso objeto senator.

Twitter Following Network

Para betweenness, os atributos indegree e outdegree não fazem diferença, pois a chegada ou a saída de edges de um nó não altera sua presença no caminho da rede. No entanto, podemos calcular a medida considerando ou não a direcionalidade da rede como um todo.

dir-c

Twitter Following Network

Podemos calcular as duas medidas e atribuí-las ao nosso objeto senator.

Exercício:

Com o código abaixo, plote a rede com a função plot() e calcule a betweenness da rede para directed = FALSE e directed = TRUE:

Exercício: resposta

Twitter Following Network

Voltando ao exemplo do Twitter:

Twitter Following Network

google

Page Rank

Twitter Following Network

Page Rank: cada nó aloca votos para nós com ele conectados.

Turbinando nossa rede

Material adicional

Tarefa da aula

As instruções da tarefa estão no arquivo NN-class-ds4ir-assignment.rmd da pasta assignment que se encontra na raiz desse projeto.